#include <bits/stdc++.h>
using namespace std;
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using ll = long long;
void solve()
{
    ll k, l1, r1, l2, r2;
    cin >> k >> l1 >> r1 >> l2 >> r2;
    ll mx = r2 / l1;
    ll qmi = 1;
    ll ans = 0;
    while(qmi<=mx)
    {
        ll L=(l2+qmi-1)/qmi;
        ll R=r2/qmi;
        ans+=max(0LL,min(R,r1)-max(L,l1)+1);
        qmi*=k;
    }
    cout << ans << "\n";
}
int main()
{
    int t = 1;
    cin >> t;
    while(t--)
    {
        solve();
    }
   return 0;
}
